package com.lmk.utils;
/**
 *数组操作工具类
 */

import java.security.SecureRandom;
import java.util.Arrays;





public class ArrayTools {
    static SecureRandom random = new SecureRandom();
    /**
     * 交换指定数字两个位置元素
     * @param array
     * @param L
     * @param R
     */
    public static void swap( int[] array, int L, int R){

        int temp;
        temp=array[L];
        array[L]=array[R];
        array[R]=temp;

    }

    /**
     * 判断元素里是否有该元素
     * @param array
     * @param number
     * @return
     */
    public  static boolean contains(int[] array, int number){
        for (int i :array ) {
            if (i==number){
                return true;
            }
        }
        return false;
    }

    /**
     * 做一个随机数组
     * @param len
     * @param min
     * @param max
     * @return
     */
    public static int[] generateArray(int len, int min, int max){
        int[] array = new int[len];
        SecureRandom random = new SecureRandom();

        int num = 0;
        for (int i = 0; i < len; i++) {
            num = min + random.nextInt(max - min);
            while (ArrayTools.contains(array, num)){
                num = min + random.nextInt(max - min);
            }
            array[i] = num;
        }

        return array;
    }

    /**
     * 判断一个数组元素是否为有序排列  默认为升序
     * @param array
     * @return
     */
    public static boolean  isSort(int[]array ){
        boolean yes=true;
        for (int i = 1; i < array.length; i++) {
            if(array[i]<array[i-1]){
                yes=false;
                break;
            }
        }return yes;
    }

    /**
     * 冒泡排序
     * @param a
     */
    public static void bubbleSort(int[]a){

        for (int i = 0; i <a.length-1 ; i++) {
            for (int j = 0; j <a.length-1-i ; j++) {
                if(a[j]>a[j+1]){
                    ArrayTools.swap(a,j,j+1);
                }
            }
        }


    }

    /**
     * 对数组进行选择排序
     * @param a
     */
    public static void selectedSort(int[]a){

        for (int i = 0; i <a.length-1 ; i++) {

            int index=0;
            for (int j = 1; j <a.length-i ; j++) {
                if(a[j]>a[index]){
                    index=j;
                    ArrayTools.swap(a,j,j+1);
                }
            }
            int last=a.length-i-1;//last为当前处理的最后一个元素
            if (index!=last){
                ArrayTools.swap(a,index,last);
            }
        }


    }

    /**
     * 差值排序
     * @param array
     */
    public  static void  testInsetSort(int[]array){
        for(int i = 1; i < array.length; i++) {  //手牌从数组中的第2个元素开始抽，也就是下标为1的元素开始，下标为0的元素当做已有手牌
            //[2]使用内层循环控制抽到的牌和手牌之间的比较和排序，只要手牌更小，就一直向前交换，直到找到合适位置，或者数组到头为止
            for(int j = i; j-1 >= 0 && array[j] < array[j-1]; j--) {
                //[3]直接进行交换，因为比较的步骤已经定义在循环条件中了
                int tmp = array[j];
                array[j] = array[j-1];
                array[j-1] = tmp;
            }



        }
    }

    /**
     * 对数组进行差值排序
     * @param array
     */
    public  static void  testInsetSort01(int[]array) {
        int j, v;
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                j = i;
                v = array[i];
                while (j > 0 && v < array[j - 1]) {
                    array[j] = array[j - 1];
                    j--;
                }


                array[j] = v;
            }
        }


    }
    /**
     * 归并排序
     * @param array
     * @return
     */
    public static int[] mergeSort(int[] array) {
        return mergeSort(array, 0, array.length - 1);
    }

    /**
     * 内部归并
     * @param array
     * @param L
     * @param R
     * @return
     */
    private static int[] mergeSort(int[] array, int L, int R) {
        int[] result;
        int size = (R - L + 1) / 2;
        if(size > 0) {
            int[] left = mergeSort(array, L, L + size - 1);
            int[] right = mergeSort(array, L + size, R);

            result = merge(left, right);
        }else {
            result = new int[] {array[L]};
        }
        return result;
    }

    /**
     * 合并算法
     * @param a
     * @param b
     * @return
     */
    private static int[] merge(int[] a, int[] b) {
        int[] c = new int[a.length + b.length];

        int left = 0;
        int right = 0;

        for(int i = 0; i < c.length; i++) {
            if(left == a.length) {
                c[i] = b[right++];
                continue;
            }

            if(right == b.length) {
                c[i] = a[left++];
                continue;
            }

            if(a[left] < (b[right])) {
                c[i] = a[left++];
            }else {
                c[i] = b[right++];
            }
        }
        return c;
    }
    /**
     * 快速排序
     * @param array
     */
    public static void quickSort(int[] array) {
        _quickSort(array, 0, array.length - 1);
    }


    /**
     * 内部快排
     * @param array
     * @param L
     * @param R
     */
    private static void _quickSort(int[] array, int L, int R) {
        if(R <= L){
            return;
        }

        int index = random.nextInt(R - L) + L;
        if(index != L) {
            swap(array, L, index);
        }


        if(L != R){
            int j = L;
            int i = L + 1;

            while(i <= R) {
                if(array[i] < array[L]) {
                    swap(array, ++j, i);
                }
                i++;
            }

            if(j != L) {
                swap(array, L, j);
                _quickSort(array, L, j - 1);
            }

            if(j != R)
                _quickSort(array, j + 1, R);
        }
    }

    /**
     * 基数排序
     * @param array
     * @return
     */
    public static void baseSort(int[] array) {
        int[][] buckets = new int[10][array.length];
        int min = 0;
        int div = 10;
        do{
            int[] bucketSize = new int[10];
            min = 0;
            for(int i = 0; i < array.length; i++) {
                // 记录最大商，以便判断时候还需要进行更高位的计算
                int temp = array[i] / div;
                if(temp > min) {
                    min = temp;
                }

                int bucket = array[i] / (div / 10) % 10;
                int bucketIndex= bucketSize[bucket];

                buckets[bucket][bucketIndex] =  array[i];
                bucketSize[bucket] = bucketIndex + 1;
            }

            div *= 10;

            int index  = 0;
            for(int i = 0; i < 10; i++) {
                for(int j = 0; j < bucketSize[i]; j++) {
                    array[index++] = buckets[i][j];
                }
            }
        }while(min > 0);
    }

}

